#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const std::vector<std::vector<T>>& vecs) {
    for (auto v : vecs) {
        for (auto n : v) std::cout << n << ", ";
        std::cout << '\n';
    }
    std::cout << '\n';
}

class Solution {
  public:
    int minPathSum(vector<vector<int>>& grid) {
        std::vector<std::vector<int>> dp(grid.size(), std::vector<int>(grid[0].size(), INT_MAX));
        dp[grid.size() - 1][grid[0].size() - 1] = grid[grid.size() - 1][grid[0].size() - 1];
        for (int i = grid.size() - 1; i >= 0; --i) {
            for (int j = grid[0].size() - 1; j >= 0; --j) {
                if (i == grid.size() - 1 and j == grid[0].size() - 1) continue;
                int left = INT_MAX, down = INT_MAX;
                if (i + 1 < grid.size()) left = dp[i + 1][j];
                if (j + 1 < grid[0].size()) down = dp[i][j + 1];
                dp[i][j] = grid[i][j] + std::min(left, down);
            }
        }
        return dp[0][0];
    }
};

int main() {
    std::vector<std::vector<int>> grid{{1, 2}, {1, 1}};
    Solution s;
    s.minPathSum(grid);
    return 0;
}
